#include "stdafx.h"
#include "GraphDescriptionReader.h"
#include "PathFlow.h"
#include <sstream>

GraphDescription::GraphDescription()
{
	setCargoAmount(0);
	setVertexList(map<string,Vertex>());
}

int GraphDescription::getCargoAmount()
{
	return cargoAmount;
}

void GraphDescription::setCargoAmount(int newCargoAmount)
{
	cargoAmount = newCargoAmount;
}

map<string,Vertex> GraphDescription::getVertexList()
{
	return vertexList;
}
void GraphDescription::setVertexList(map<string,Vertex> newVertexList)
{
	vertexList = map<string,Vertex>(newVertexList);
}

void GraphDescription::addVertex(Edge edge)
{	
	if (vertexList.find(edge.start) == vertexList.end()) //jesli wierzcholek bedacy poczatkiem krawedzi nie znajduje sie na liscie dodaj go
	{
		Vertex vertex = Vertex();
		vertex.setName(edge.start);
		vertexList[edge.start]= vertex;
		
	}
	if (vertexList.find(edge.end) == vertexList.end())//jesli wierzcholek bedacy koncem krawedzi nie znajduje sie na liscie dodaj go
	{
		Vertex vertex = Vertex();
		vertex.setName(edge.end);
		vertexList[edge.end]= vertex;
	}
	vertexList[edge.start].addNextVertex(&vertexList[edge.end]); //dodaj do wierzcholka bedacego poczatkiem krawedzi wskazanie na wierzcholek bedacy jej krancem
	vertexList[edge.end].addEdge(edge.start,edge.capacity); //dodaj do wierzcholka bedacego koncem krawedzi krawedz pozwalajaca na dojscie do niego z wierzcholka poczatkowego tej krawedzi
	vertexList[edge.start].setOutputSum(vertexList[edge.start].getOutputSum() + edge.capacity); //do wierzcholka poczatkowego dodaj do jego towaru wyjsciowego przepustowosc nowej krawedzi
	vertexList[edge.end].setInputSum(vertexList[edge.end].getInputSum() + edge.capacity); //do wierzcholka koncowego dodaj do jego towaru wejsciowego przepustowosc nowej krawedzi
}

void GraphDescription::readGraphDescription(string fileName)
{
	GraphDescriptionReader reader = GraphDescriptionReader(fileName); //stworz nowy obiekt wczytujacy opis grafu
	reader.readGraphDescriptionFile(this); //wczytaj opis grafu
}

void GraphDescription::printVertexes() //wypisz wierzcholki
{
	map<string,Vertex> copy = map<string,Vertex>(vertexList);
	for (int i=0, size = copy.size(); i< size; i++) //iterujac po mapie wierzcholkow wypisz je
	{
		Vertex vertex = (*copy.begin()).second;
		copy.erase(copy.begin());
		std::cout << vertex.getName() + " ";
		std::cout << vertex.getInputSum();
		std::cout << " ";
		std::cout << vertex.getOutputSum();
		std::cout << "\n";
	}
}

std::pair<string,string> GraphDescription::tryHybridize(PathFlow* flowPath){
	list<string>::iterator vIt;
	for (vIt = flowPath -> path.begin(); vIt != flowPath->path.end(); vIt++){		
		if ( ( (*vIt) != "S") && ((*vIt) != "T") ){
			string pathThroughtVertexStr = "";
			if ( (pathThroughtVertexStr = canHybridizeInVertex(flowPath,&vertexList[*vIt])) != "" ){
				/*return std::pair<PathFlow*,Vertex*>(pathThroughtVertex,&vertexList[*vIt]);*/
				return std::pair<string,string>(pathThroughtVertexStr,*vIt);
			}
		}		
	}

	return std::pair<string,string>("","");
}

//to musi sie stac przed dodaniem tej sciezki
///* dla kazdego wierzcholka na znalezionej sciezce */
//for ( pathVertexIt = flowPath -> begin(); pathVertexIt != flowPath -> end(); flowPath++){
string GraphDescription::canHybridizeInVertex(PathFlow* newFlowPath, Vertex* vertex)
{
	list<string>::iterator pathVertexIt;
	
	/* dla kazdej pary krawedzi dochodzacych */
	/*list<PathFlow*>::iterator inPathIt = vertex->inPaths.begin();*/
	map<string,PathFlow*>::iterator inPathIt = vertex->inPathMap.begin();
		

	

	for ( inPathIt; inPathIt != vertex->inPathMap.end(); ++inPathIt){		
			/* paths can be swapped */						
		if ( (inPathIt->second)->flow == (newFlowPath)->flow ){
				
				int inLengthPath  = (inPathIt->second)->getLengthTo(vertex->name);
				int inNewFlowPathLength  = newFlowPath->getLengthTo(vertex->name);
				int outLengthPath = (inPathIt->second)->getLengthFrom(vertex->name);
				int outNewFlowPathLength = newFlowPath->getLengthFrom(vertex->name);
															
				int outPath1Length = inLengthPath + outNewFlowPathLength;
				int outPath2Length  = inNewFlowPathLength + outLengthPath;
				
				int beforeMaxLength =  (inPathIt->second)-> getLength() > newFlowPath -> getLength() ? (inPathIt->second) -> getLength()  : newFlowPath-> getLength();
				int afterMaxLength = outPath1Length > outPath2Length ? outPath1Length : outPath2Length;

				 if ( afterMaxLength <  beforeMaxLength ) {		
					 cout << "Swapping paths in " << vertex->name << std::endl;
					 return (inPathIt->first);
				 }
				 
			}											
	}
	

	return "";
}

void GraphDescription::hybridize(string flowPath1Str, PathFlow* flowPath2, string vertexStr){
	
	Vertex* vertex = &vertexList[vertexStr];
	PathFlow* flowPath1 = vertex->inPathMap[flowPath1Str];	

	list<string>::iterator vIt1;
	list<string>::iterator vIt2;
	list<string> out1 = list<string>();
	list<string> out2 = list<string>();

	for ( vIt1 = flowPath1->path.begin(); (*vIt1) != vertex->name; ++vIt1 ){
		out1.push_back((*vIt1));		
	}
	
	for ( vIt2 = flowPath2->path.begin(); (*vIt2) != vertex->name ; ++vIt2 ){
		out2.push_back((*vIt2));
	}

	out1.push_back((*vIt1));
	out2.push_back((*vIt2));
	vIt1++; 
	vIt2++; 


	for ( ; vIt1 != flowPath1->path.end(); ++vIt1 ){
		out2.push_back((*vIt1));
		Vertex v = vertexList[(*vIt1)];
		v.inPathMap.erase(flowPath1->toString());		
		v.inPathMap[flowPath2->toString()] = flowPath2;
	}
	
	for ( ; vIt2 != flowPath2->path.end(); ++vIt2 ){
		out1.push_back((*vIt2));		
		Vertex v = vertexList[(*vIt2)];
		v.inPathMap.erase(flowPath2->toString());		
		v.inPathMap[flowPath1->toString()] = flowPath1;
	}

	flowPath1->path = out1;
	flowPath2->path = out2;
	return ;
}

void GraphDescription::takeFlowFromPath(PathFlow* flowPath){
	list<string> path = flowPath->path;
	int flow = flowPath->flow;

	string v_prev;
	/* decrease capacity and remove edge when not exist */
	for ( list<string>::iterator it = path.begin(); it != path.end() ; it++){			
		if ( it != path.begin() ){
			/*std::cout <<  "(" << *it << " , " << v_prev << ") = " << vertexList[*it].edges[v_prev]  << std::endl;			*/
			vertexList[*it].edges[v_prev] = vertexList[*it].edges[v_prev] - flow;
			/*vertexList[*it].inPaths.push_back(flowPath);*/ //TODO
			vertexList[*it].inPathMap.insert(std::pair<string,PathFlow*>(flowPath->toString(),flowPath));
			/*std::cout << "after " << vertexList[*it].edges[v_prev]  << std::endl;*/
		
			if ( vertexList[*it].edges[v_prev] == 0){				
				vertexList[*it].edges.erase(v_prev);
				vertexList[v_prev].nextVertexes.remove(&vertexList[*it]);				
				if ( vertexList[v_prev].nextVertexes.size() == 0 ){
					vertexList.erase(v_prev);
				}
			}
		}
		v_prev = (*it);
	}

	return ;

}


PathFlow* GraphDescription::shortestPath(int maxAmountToSent){	
	/* inicjalizacja */
	map<string,Vertex> vertexes = map<string,Vertex>(vertexList);
	map<string,int> dist = map<string,int>();
	map<string,string> previous = map<string,string>();
	Vertex source = vertexList["S"];
	Vertex target = vertexList["T"];	

	for (map<string,Vertex>::iterator it = vertexes.begin(); it != vertexes.end(); it++) 
	{
		dist[it->first] = INF;
		previous[it->first] = "?"; //oznacza ze poprzednik jest niezdefiniowany
	}
	dist["S"] = 0;							// Distance from source to source	 

	/* Algorytm Dijkstry */
	map<string,Vertex> Q = map<string,Vertex>(vertexes);
	while (!Q.empty()){                  // The main loop
		string u_key = getMinnimalDistance(Q,dist);	
		/*std::cout << "min distnace to" << u_key << std::endl;*/
        if (dist[u_key] == INF){
			return NULL;                     // all remaining vertices are inaccessible from source		   
		}
		if( u_key == "?"){
			/*return std::pair<list<string>, int>(new list<string>(), 0);*/
			return NULL;
		}
		
		Q.erase(u_key);	
	
		Vertex u = vertexList[u_key];
			
		int alt;
		for (list<Vertex*>::iterator v_it = u.nextVertexes.begin(); v_it != u.nextVertexes.end(); v_it++){			
			Vertex* v = *v_it;
			int alt = dist[u_key] +1; //+ v -> edges[u_key];
			string v_key = v -> name;
			if ( alt < dist[v_key] ){
				dist[v_key] = alt ;
                previous[v_key] = u_key;				
                /*decrease-key v in Q; */      // Reorder v in the Queue
			}
		}
	}


	
	 /* Construct shortest path flow */
	 list<string> shortestPath = list<string>();
	 string u_key = target.name;

	
	 while (u_key != "?"){
		 shortestPath.push_front(u_key);
		 u_key = previous[u_key];
	 }			

	int pathMaxFlow = INF;
	string v_prev;

	for ( list<string>::iterator it = shortestPath.begin(); it != shortestPath.end() ; it++){		
		if ( it != shortestPath.begin() ){		
			int edgeFlow = vertexList[*it].edges[v_prev];
			pathMaxFlow =  edgeFlow < pathMaxFlow ? edgeFlow : pathMaxFlow;
		}				
		v_prev = (*it);		
	}	

	if ( pathMaxFlow > maxAmountToSent ){
		pathMaxFlow = maxAmountToSent;
	}

	return new PathFlow(shortestPath, pathMaxFlow);
}

string GraphDescription::getMinnimalDistance(map<string,Vertex> Q, map<string,int> dist){
		
	int minDist = INF;
	string vertexId = "?";
	for (map<string,Vertex>::iterator it = Q.begin(); it != Q.end(); it++){
		if ( dist[it->first] < minDist){
			vertexId = it -> first;
			minDist = dist[vertexId];
		}
	}
	return vertexId;
}

void GraphDescription::printResults(ostream& outStream, list<PathFlow*> flowDecompositionPaths){
		
	   std::cout << "\nchoosen routes:\n";
	   int maxRouteSize = 0;
	   for (list<PathFlow*>::iterator it = flowDecompositionPaths.begin(); it != flowDecompositionPaths.end(); ++it){
			for ( list<string>::iterator listIt = (*it)->path.begin() ; listIt != (*it)->path.end() ; listIt++){
				if ( listIt != (*it)->path.begin() ){
					outStream << " ";
				}		
				outStream << (*listIt);
			}

			if ( (*it)->path.size()  > maxRouteSize){
				maxRouteSize = (*it)->path.size();
			}

			outStream << " : " << ((*it)->flow) << "\n";
	   }	   
	   
	  std::cout << "Length of max route: ";
	  std::cout << (((maxRouteSize-1) < 0) ? 0 : (maxRouteSize-1)) << std::endl;
	  std::cout << "\n";

}


void GraphDescription::shortestPaths(){			

	   list<PathFlow*> flowDecompositionPaths = list<PathFlow*>();

	   int notSentAmount = cargoAmount;
	   list<std::pair<list<string>, int> >* allPaths = new list<std::pair<list<string>, int> >();
	   
	   std::cout << "Cargo to transport: ";
	   std::cout << cargoAmount << std::endl;

	   PathFlow* shortestPathFlow;	   
	   while( notSentAmount > 0 && (shortestPathFlow = shortestPath(notSentAmount)) ){		   
		   flowDecompositionPaths.push_back(shortestPathFlow);
		   notSentAmount = notSentAmount - shortestPathFlow->flow;		   
		   takeFlowFromPath(shortestPathFlow);
	   }

	   printResults(cout,flowDecompositionPaths);

	   ofstream outputFile;
	   outputFile.open("output.txt");
	   printResults(outputFile,flowDecompositionPaths);	   
	   outputFile.close();

      return ;
}



void GraphDescription::shortestPathsWithHybridization(){			

	   list<PathFlow*> flowDecompositionPaths = list<PathFlow*>();

	   int notSentAmount = cargoAmount;
	   list<std::pair<list<string>, int> >* allPaths = new list<std::pair<list<string>, int> >();
	   
	   std::cout << "Cargo to transport: ";
	   std::cout << cargoAmount << std::endl;

	   PathFlow* shortestPathFlow;	   
	   while( notSentAmount > 0 && (shortestPathFlow = shortestPath(notSentAmount)) ){		   
		   flowDecompositionPaths.push_back(shortestPathFlow);
		   notSentAmount = notSentAmount - shortestPathFlow->flow;		   
		   std::pair<string,string> p = tryHybridize(shortestPathFlow);
		   if ( p.first != "" && p.second != ""){
			   std::cout <<  "SHORTEST PATH " << shortestPathFlow->toString() << std::endl;
			   std::cout << "HYBRIDIZE : "<< p.first << " -> " << p.second << std::endl;
			   hybridize(p.first,shortestPathFlow,p.second);								
		   }		   

		   takeFlowFromPath(shortestPathFlow);
	   }


	   printResults(cout,flowDecompositionPaths);

	   ofstream outputFile;
	   outputFile.open("output.txt");
	   printResults(outputFile,flowDecompositionPaths);	   
	   outputFile.close();

      return ;
}


bool GraphDescription::verifyGraphDescription() //zweryfikuj poprawnosc grafu
{
	
	if (vertexList["S"].getInputSum() != 0) //sprawdz czy wyjscie z S jest > 0
		return false;
	if (vertexList["T"].getOutputSum() != 0) //sprawdz czy towar wchodzacy do T > 0
		return false;
	if (vertexList["T"].getInputSum() < cargoAmount) // sprawdz czy towar wplywajacy do T jest conamniej rowny ilosci ktora trzeba przeslac 
		return false;
	
	map<string,Vertex> copy = map<string,Vertex>(vertexList);
	
	for (int i=0, size = copy.size(); i< size; i++) //iterujac po wierzcholkach sprawdz prawo kirchoffa
	{
		Vertex vertex = (*copy.begin()).second;
		copy.erase(copy.begin());
		if (vertex.getInputSum() != vertex.getOutputSum() && vertex.getName() != "T" && vertex.getName() != "S")
			return false;
	}
	return true;
}

void GraphDescription::setStartRoute() //ustaw 1 wierzcholek w liscie ze scierzkami "dojsciami" do wierzcholkow
{
	vertexList["S"].addRoute("S",vertexList["S"].getOutputSum());
	list<string> l = list<string>();
	l.push_back("S");
	vertexList["S"].routeList.push_back(pair<list<string>,int>(l,vertexList["S"].getOutputSum()));
}

void GraphDescription::setStartRouteFlowMethod() //ustaw 1 wierzcholek w liscie ze scierzkami "dojsciami" do wierzcholkow dla metody 2
{
	int max =0;
	string maxName;
	int suma =0;
	map<string, int> mapa = map<string, int>(vertexList["T"].getEdges());
	for (int i = mapa.size(); 0 < mapa.size();)
	{
		suma += mapa.begin()->second;
		if (i == mapa.size())
		{
			maxName = mapa.begin()->first;
			max = mapa.begin()->second;
		}
		if (max < mapa.begin()->second)
		{
			maxName = mapa.begin()->first;
			max = mapa.begin()->second;
		}
		mapa.erase(mapa.begin());
	}

	int cargo = getCargoAmount();
	if ((suma - max  < max) && (max >= cargo))
	{
		list<string> l = list<string>();
		l.push_back("T");
		vertexList[maxName].routeList.push_back(pair<list<string>,int>(l,vertexList[maxName].getOutputSum()));
		describeVertexesFlowMethod(&vertexList[maxName]);
		findRoutes("S");
	}
	else
	{
		std::cout << "Graph don't have requirements for this method. Using full scan.\n";
		setStartRoute();
		describeVertexes(&vertexList["S"]);
		findRoutes("T");
	}

}

void GraphDescription::describeVertexes(Vertex* startVertex)
{
	if (startVertex->getName() == "T") //jesli doszedles do T skoncz
		return;

	list<Vertex*> copy = list<Vertex*>(startVertex->getNextVertexes());
	
	for (int i=0, size = copy.size(); i < size; i++) //iterujac po wierzcholkach 
	{
		Vertex* vertex = (Vertex*)(copy.front());
		copy.pop_front();
			
		list<std::pair<list<string>,int>> routeCopy = list<std::pair<list<string>,int>>(startVertex->routeList);
		//map<string,int> routeCopy = map<string,int>(startVertex->getRoutes());
	
		for (int j=0, size = routeCopy.size(); j< size; j++) //iteruj ich nastepne wierzcholki
		{
			std::pair<list<string>,int> para = routeCopy.front();
			routeCopy.erase(routeCopy.begin());
			for (list<string>::iterator t = para.first.begin(); t != para.first.end(); t++)
			{
				if (t->compare(vertex->getName()) == 0)
					throw new exception();
			}
			if (vertex->getEdges()[startVertex->getName()] <= para.second) //do wierzcholka bedacego nastepnikiem badanego dopisz sciezke skladajaca sie ze sciezki wierzcholka badanego powiekszona o nazwe tego wierzcholka oraz jesli krawedz je laczaca posiada mniejsza przepustowosc niz minimalna z poprzednich krawedzi zastap ja ta wartoscia, w innym wypadku wybierz poprzednia
				para.second = vertex->getEdges()[startVertex->getName()];
			else
				para.second = para.second; //zostaje stara wartosc
			para.first.push_back(vertex->getName());
				bool zawiera = false;
			for (list<std::pair<list<string>,int>>::iterator t = vertex->routeList.begin(); t != vertex->routeList.end(); t++)
			{
				if (t->first == para.first && t->second == para.second)
					zawiera = true;
			}
			if (!zawiera)
				vertex->routeList.push_back(para);
		}
		describeVertexes(vertex);
	}
}

void GraphDescription::findRoutes(string vertexName) //szukanie najkrotszych scierzek
{
	list<std::pair<list<string>,int>> copy = list<std::pair<list<string>,int>>(vertexList[vertexName].routeList);

	list<std::pair<list<string>,int>> sorted = list<std::pair<list<string>,int>>();
	list<std::pair<list<string>,int>>::const_iterator iterator;
	while (copy.size() > 0) //posortuj wierzcholki rosnaco wg dlugosci
	{
		std::pair<list<string>,int> para = (*copy.begin());
		list<string> minPath = para.first;
		int minVal = para.second;
		for (iterator = copy.begin(); iterator != copy.end(); iterator++)
		{
			if (iterator->first.size() < minPath.size())
			{
				minPath = iterator->first;
				minVal = iterator->second;
			}
		}
		sorted.push_back(pair<list<string>,int>(minPath,minVal));
		para = std::pair<list<string>,int>(minPath,minVal);
		copy.remove(para);
	}
	ofstream outputFile;
	outputFile.open("output.txt");
	int inputCapacity = cargoAmount;
	std::cout << "Cargo to transport: ";
	std::cout << inputCapacity;
	std::cout << "\nchoosen routes:\n";
	for (list<std::pair<list<string>,int>>::iterator iterator = sorted.begin(); iterator != sorted.end(); iterator ++) //przechodzac po kolei sciezki wypisuj je wraz z przepustowoscia i odejmuj ja od ilosci towaru w celu wyliczenia pozostalej jego ilosci do przeslania
	{
		if (inputCapacity > 0 && iterator->second > 0)
		{
			for (list<string>::iterator T = iterator->first.begin(); T != iterator->first.end(); T++)
			{
					std::cout << *T + " ";
					outputFile << *T + " ";
			}

			
			if (iterator->second < inputCapacity)
			{
				std::cout << iterator->second;
				outputFile << iterator->second;
			}
			else
			{
				std::cout << inputCapacity;
				outputFile << inputCapacity;
			}
			std::cout << "\n";
			outputFile << "\n";
			inputCapacity -= iterator->second;
			
			if (inputCapacity <= 0)
			{
				std::cout << "Length of max route: ";
				std::cout << iterator->first.size()-1;
				std::cout << "\n";
				outputFile.close();
				return;
			}
			for (list<std::pair<list<string>,int>>::iterator tmp = list<std::pair<list<string>,int>>::iterator(iterator); tmp != sorted.end(); tmp++) //wyszukaj scierzki zawierajace sie w sobie i
				//uaktulanij przeplywy po wybraniu jednej z nich
			{
				for (list<string>::iterator T = iterator->first.begin(); T != iterator->first.end(); T++) //iteruj po wierzcholkach wybranej scierzki
				{
					bool zawiera = false;
					for (list<string>::iterator t = tmp->first.begin(); t != tmp->first.end(); t++)
					{
						list<string>::iterator Tcopy = list<string>::iterator(T);
						list<string>::iterator tcopy = list<string>::iterator(t);
						Tcopy++;
						tcopy++;
						if (*t != "T" && *T != "T")
							if (t->c_str() == T->c_str() && tcopy->c_str() == Tcopy->c_str())
								zawiera = true;
					}
					
					if (zawiera && tmp->first != iterator->first && T->compare("T") == 0 ) //jesli 2 kolejne wierzcholki zostaja wykryte
						// w innych scierzkach pomniejsz je o przepustowosc obecnie wybranego
					{
						map<string, Vertex> mapa = map<string, Vertex>(getVertexList());
						stringstream ss;
						string buff;
						ss << T->c_str();
						ss >> buff;
						mapa[buff].setInputSum(mapa[buff].getInputSum() - iterator->second);
						mapa[buff].setOutputSum(mapa[buff].getOutputSum() - iterator->second);
						ss.clear();
						list<string>::iterator Tcopy = list<string>::iterator(T);
						Tcopy++;
						ss << Tcopy->c_str();
						ss >> buff;
						mapa[buff].setInputSum(mapa[buff].getInputSum() - iterator->second);
						mapa[buff].setOutputSum(mapa[buff].getOutputSum() - iterator->second);
						
						int newFlow =0;
						for (list<string>::iterator t = tmp->first.begin(); t != tmp->first.end(); t++)
						{
							ss.clear();
							ss << t->c_str();
							ss >> buff;
							if (t == tmp->first.begin())
								newFlow = mapa[buff].getOutputSum();
							if (newFlow > mapa[buff].getOutputSum() && buff != "T")
								newFlow = mapa[buff].getOutputSum();
						}

 						tmp->second = newFlow;
						if (tmp->second < 0)
							tmp->second = 0;
						break;
					}
				}
			}
		}
	}
	if (inputCapacity > 0 ) //jesli zostal towar to znaczy ze mamy maksymalny przeplyw i nie da sie wiecej przeslac - trzeba rozbudowac graf
	{
		std::cout << "Can't send more cargo. Maximum flow is: ";
		std::cout << cargoAmount - inputCapacity;
		std::cout << " and Cargo number: ";
		std::cout << cargoAmount;
		std::cout << ".\nGraph needs to extended.\n";
	}
	outputFile.close();
}

void GraphDescription::describeVertexesFlowMethod(Vertex* startVertex)
{

	if (startVertex->getName() == "S") //jesli doszedles do A skoncz
	{
		list<std::pair<list<string>,int>> routeCopy = list<std::pair<list<string>,int>>(startVertex->routeList);
		for (list<std::pair<list<string>,int>>::iterator it = routeCopy.begin(); it != routeCopy.end(); it++) //iteruj ich nastepne wierzcholki
		{
			std::pair<list<string>,int> para = std::pair<list<string>,int>(it->first,it->second);
	
			bool zawiera = false;
			for (list<string>::iterator strIt = para.first.begin(); strIt != para.first.end();strIt++)
			{
				if (strIt->compare("S") == 0)
					zawiera = true;
			}
			if (!zawiera)
			{
				para.first.push_front("S");
				Vertex* vertex = &vertexList["S"] ;
				vertex->routeList.clear();
				vertex->routeList.push_front(para);
			}
		}
		return;
	}

	map<string,int> copy = map<string,int>(startVertex->getEdges());
	
	for (int i=0, size = copy.size(); i < size; i++) //iterujac po wierzcholkach 
	{
		
		string vertexName = copy.begin()->first;
		int vertexEdgeCap = copy.begin()->second;
		copy.erase(copy.begin());

		//map<string,int> routeCopy = map<string,int>(startVertex->getRoutes());
		list<std::pair<list<string>,int>> routeCopy = list<std::pair<list<string>,int>>(startVertex->routeList);
		for (list<std::pair<list<string>,int>>::iterator it = routeCopy.begin(); it != routeCopy.end(); it++) //iteruj ich nastepne wierzcholki
		{
			std::pair<list<string>,int> para = std::pair<list<string>,int>(it->first,it->second);
	
			bool zawiera = false;
			for (list<string>::iterator strIt = para.first.begin(); strIt != para.first.end();strIt++)
			{
				if (strIt->compare(vertexName) == 0)
					zawiera = true;
			}
			if (vertexEdgeCap <= para.second) //do wierzcholka bedacego nastepnikiem badanego dopisz sciezke skladajaca sie ze sciezki wierzcholka badanego powiekszona o nazwe tego wierzcholka oraz jesli krawedz je laczaca posiada mniejsza przepustowosc niz minimalna z poprzednich krawedzi zastap ja ta wartoscia, w innym wypadku wybierz poprzednia
			{
				para.second = vertexEdgeCap;
			}
			else
			{
				para.second = para.second;

			}
			if (!zawiera)
			{
				para.first.push_front(startVertex->getName());
				Vertex* vertex = &vertexList[vertexName] ;
				list<std::pair<list<string>,int>> c = list<std::pair<list<string>,int>>(vertex->routeList);
				c.remove(para);
				if (c.size() == vertex->routeList.size())
					vertex->routeList.push_back(para);
				else 
					return;
			}

		}
		describeVertexesFlowMethod(&getVertexList()[vertexName]);
	}

}

void GraphDescription::printGrpah(ostream& outStream){

	   outStream << cargoAmount << "\n";
	   for (map<string,Vertex>::iterator vIt = vertexList.begin(); vIt != vertexList.end(); ++vIt){
		   Vertex v = vIt->second;		   
		   for (map<string,int>::iterator eIt = v.edges.begin() ; eIt != v.edges.end(); ++eIt){
			   outStream << eIt->first << " " << vIt->first <<  " " << eIt->second << "\n";
		   }		   
	   }	   	   	  
}
	

